package dynamicProgramming.MatrixPathProblem;

/**
 * @author zxc
 * @date 2023/01/24 16:25
 **/

/**
 * 题目 ：最小路径之和
 * 题目详述 ：
 * 给定一个包含非负整数的 mxn网格grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：一个机器人每次只能向下或者向右移动一步。
 *
 * 提示：
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 200
 * 0 <= grid[i][j] <= 100
 */
public class MinPathSum {
    /**
     * 思路 ：
     * 假设f(i,j)为当前坐标位置（i ， j）到坐标位置（0 ，0）最少路径成本;
     *
     * 状态转移方程 ：
     * 1.特殊情况 :
     * （1）若是i == 0的话，那么只能够向右移动;
     * ===》 temp[0][j] = temp[0][j - 1] + grid[0][j];
     * （2）若是j == 0的话，那么只能够向下移动;
     * ===> temp[i][0] = temp[i - 1][0] + grid[i][0];
     * 2.通常情况
     * 即，对于i > 0 && j > 0的情况下,
     * ===》 即，f(i,j)有两种得法 ：a.f(i-1,j)向右移动一步; b.f(i,j-1)向下移动一步;
     * temp[i][j] = Math.min(temp[i][j - 1],temp[i - 1][j]) + grid[i][j];
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        // 二维数组grid的行数;
        int row = grid.length;
        // 二维数组grid的列数;
        int col = grid[0].length;
        // 由于要求取f(i,j)的话，只需要知道f(i-1,j)和f(i,j-1)即可;
        // ===> 所以可以通过使用 2行n列的二维数组来存储计算结果即可;
        int[][] temp = new int[2][col];
        // 初始化temp[0][0]元素
        temp[0][0] = grid[0][0];
        // 即，当i == 0时，只能够向右走;
        for(int j = 1;j < col;j++){
            temp[0][j] = temp[0][j - 1] + grid[0][j];
        }
        // 通常情况 ：
        // temp[i % 2][j] = Math.min(temp[i % 2][j - 1],temp[(i - 1) % 2][j]) + grid[i][j];
        for(int i = 1;i < row;i++){
            // 由于每一行首个元素的值temp[i][0]未能够在内层for循环中获取,所以在外层for循环和内层for循环之间对于其进行赋值;
            temp[i % 2][0] = temp[(i - 1) % 2][0] + grid[i][0];
            for(int j = 1;j < col;j++){
                temp[i % 2][j] = Math.min(temp[i % 2][j - 1],temp[(i - 1) % 2][j]) + grid[i][j];
            }
        }
        return temp[(row - 1) % 2][col - 1];
    }
}
